package 简单.字符串;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
 * <p>
 * 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
 * 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
 * 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
 * 类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
 * <p>
 * depth("") = 0
 * depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
 * depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
 * depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串
 * 例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")
 * (" 、"(()" 都不是 有效括号字符串 。
 * <p>
 * 给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-the-parentheses
 */
public class 括号的最大嵌套深度_1614 {

    public static void main(String[] args) {

        String str = "8*((1*(5+6))*(8/6))";
        String s = "(5/(2/8))*(((4-1+9/1)*3)/(2+5))-4-1+5+2*(4/3-7)";
        String s1 = "(1+2)/(5+((4-9+8)*((1+8+(5*7)*4)/(7+9-5)))/(7/3-8-4-8))";
        System.out.println(maxDepth(s1));

    }

    /**
     * 栈
     * 遍历，碰到(进栈，碰到)，弹出一个(，记录栈中(的最大数量
     *
     * @param s
     * @return
     */
    public static int maxDepth(String s) {
        int maxCount = 0;
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.addFirst(s.charAt(i));
                maxCount = Math.max(maxCount, stack.size());
            }
            if (s.charAt(i) == ')') {
                stack.pollFirst();
            }
        }
        return maxCount;
    }

    /**
     * 栈中存的数据是没有意义的，只需要知道最大数量
     *
     * @param s
     * @return
     */
    public static int efficientMaxDepth(String s) {
        int maxCount = 0;
        int curCount = 0;  //用一个变量来模拟栈的元素个数
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                curCount++;
                maxCount = Math.max(maxCount, curCount);
            }
            if (s.charAt(i) == ')') {
                curCount--;
            }
        }
        return maxCount;
    }

}
